package cn.edu.leetcode.买卖股票的最佳时机;

public class 买卖股票的最佳时机4 {
    public static int maxProfit(int k, int[] prices) {
        if (prices.length <= 1 || k == 0) return 0;
        int n = prices.length;
        k = Math.min(k, n / 2);
        int[][] profit = new int[2 * k][n]; // profit[0] 第一次买入；profit[1] 第一次卖出； 买入卖出动态规划
        for (int i = 0; i < k; i++) {
            profit[2 * i][0] = -prices[0];  //买入
            profit[2 * i + 1][0] = 0;  //卖出
        }
        for (int i = 1; i < n; i++) {
            if (k >= 1) {
                profit[0][i] = Math.max(profit[0][i - 1], -prices[i]);  //第一次买入最大利润
                profit[1][i] = Math.max(profit[1][i - 1], profit[0][i] + prices[i]);  // 第一次卖出最大利润
            }
            for (int j = 1; j < k; j++) {
                profit[2 * j][i] = Math.max(profit[2 * j][i - 1], profit[2 * j - 1][i] - prices[i]);  //第j次买入最大利润
                profit[2 * j + 1][i] = Math.max(profit[2 * j + 1][i - 1], profit[2 * j][i] + prices[i]);  //第j次卖出最大利润
            }
        }
        return profit[2 * k - 1][n - 1];
    }

    public static void main(String[] args) {
        System.out.println(maxProfit(2, new int[]{7, 1, 5, 3, 6, 4}));
    }
}
